package seqlist.link.leetcode;

/**
 * @author yuisama
 * @date 2023/03/19 11:43
 * 合并两个链表
 **/
public class Num21_MergeTwoLists {
    // 1.基础做法，迭代法
//    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
//        // 1.base case
//        if(list1 == null) {
//            return list2;
//        }
//        if (list2 == null) {
//            return list1;
//        }
//        ListNode dummyHead = new ListNode();
//        ListNode tail = dummyHead;
//        // 当l1和l2都不为空时，取较小值拼接在新链表的尾部
//        while (list1 != null && list2 != null) {
//            if (list1.val <= list2.val) {
//                tail.next = list1;
//                tail = list1;
//                list1 = list1.next;
//            }else {
//                tail.next = list2;
//                tail = list2;
//                list2 = list2.next;
//            }
//        }
//        // 此时至少有一个链表为空
//        if (list1 == null) {
//            tail.next = list2;
//        }
//        if (list2 == null) {
//            tail.next = list1;
//        }
//        return dummyHead.next;
//    }
    // 2.递归
    // 传入两个以list1和list2为头节点的链表，就能将这两个链表合并为一个大的升序链表
    // 并返回新的头节点
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // 1.base case
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        if(list1.val <= list2.val) {
            // 合并list1从第二个节点开始的子链表和整个list2
            list1.next = mergeTwoLists(list1.next,list2);
            return list1;
        }else {
            list2.next = mergeTwoLists(list1,list2.next);
            return list2;
        }
    }
}